// 深度优先遍历
export function traverseDFS(node, callback, depth = 0) {
  callback(node, depth);
  if (node.children && node.children.length > 0) {
    node.children.forEach(child => {
      traverseDFS(child, callback, depth + 1);
    });
  }
}

// 广度优先遍历
export function traverseBFS(root, callback) {
  const queue = [{ node: root, depth: 0 }];
  
  while (queue.length > 0) {
    const { node, depth } = queue.shift();
    callback(node, depth);
    
    if (node.children && node.children.length > 0) {
      node.children.forEach(child => {
        queue.push({ node: child, depth: depth + 1 });
      });
    }
  }
}

// 查找节点
export function findNode(root, nodeId) {
  let result = null;
  
  traverseDFS(root, (node) => {
    if (node.id === nodeId) {
      result = node;
    }
  });
  
  return result;
}

// 查找父节点
export function findParent(root, nodeId) {
  let parent = null;
  
  function findParentRecursive(node, targetId) {
    if (node.children && node.children.length > 0) {
      for (const child of node.children) {
        if (child.id === targetId) {
          parent = node;
          return true;
        }
        if (findParentRecursive(child, targetId)) {
          return true;
        }
      }
    }
    return false;
  }
  
  findParentRecursive(root, nodeId);
  return parent;
}

// 获取所有叶子节点
export function getLeafNodes(root) {
  const leaves = [];
  
  traverseDFS(root, (node) => {
    if (!node.children || node.children.length === 0) {
      leaves.push(node);
    }
  });
  
  return leaves;
}

// 获取节点路径
export function getNodePath(root, nodeId) {
  const path = [];
  
  function findPath(node, targetId) {
    path.push(node);
    
    if (node.id === targetId) {
      return true;
    }
    
    if (node.children && node.children.length > 0) {
      for (const child of node.children) {
        if (findPath(child, targetId)) {
          return true;
        }
      }
    }
    
    path.pop();
    return false;
  }
  
  findPath(root, nodeId);
  return path;
}

// 过滤树节点
export function filterTree(root, predicate) {
  function filterNode(node) {
    if (predicate(node)) {
      const newNode = { ...node };
      if (node.children && node.children.length > 0) {
        newNode.children = node.children
          .map(filterNode)
          .filter(child => child !== null);
      }
      return newNode;
    }
    
    if (node.children && node.children.length > 0) {
      const filteredChildren = node.children
        .map(filterNode)
        .filter(child => child !== null);
      
      if (filteredChildren.length > 0) {
        return {
          ...node,
          children: filteredChildren
        };
      }
    }
    
    return null;
  }
  
  return filterNode(root);
}

// 生成唯一ID
export function generateId() {
  return `node_${Date.now()}_${Math.random().toString(36).substr(2, 9)}`;
}